package com.li.arithmetic.tree;

import java.util.LinkedList;
/**
 * 二叉排序树的基本操作
 * @author lichuangen
 *
 */
public class BinaryTree {
	private Node root = null;

	public Node initTree(int data){
		if(root == null){
			root = new Node(data);
			root.left = null;
			root.right = null;
			return root;
		}else{
			return root;
		}
	}
	
	public void addNode(int data){
		Node node = new Node(data);
		if(root !=null){
		Node current = root;
		Node parent = null;
		while(true){
			if(data <= current.data){
				parent = current;
				current = parent.left;
				if(current == null){
					parent.left = node;
					break;
				}
			}else if(data > current.data){
				parent = current;
				current = parent.right;
				if(current == null){
					parent.right = node;
					break;
				}
			}
		}
		}
	}
	
	public Node findNode(Node root,int data){
		if(root == null){
			return null;
		}else{
			if(data == root.data){
				return root;
			}else if(data < root.data && root.left!=null){
				return findNode(root.left,data);
			}else if(data > root.data && root.right!=null){
				return findNode(root.right,data);
			}
		}
		return root;
	}
	
	public Node getLeftNode(Node parent){
		if(parent!=null){
			return parent.left;
		}else{
			return null;
		}
	}
	
	public Node getRightNode(Node parent){
		if(parent!=null){
			return parent.right;
		}else{
			return null;
		}
	}
	
	public int getTreeDepth(Node root){
		int depleft,depright;
		if(root == null){
			return 0;
		}else{
			depleft = getTreeDepth(root.left);
			depright = getTreeDepth(root.right);
			if(depleft > depright){
				return depleft+1;
			}else{
				return depright+1;
			}
		}
	}
	
	public void clearTree(Node node){
		if(node!=null){
			clearTree(node.left);
			clearTree(node.right);
			node = null;
		}
	}
	
	public void levelTree(Node root){
		if(root == null){
			return;
		}else{
			LinkedList<Node> queue = new LinkedList<Node>();
			Node current = null;
			queue.offer(root);
			while(!queue.isEmpty()){
				current = queue.poll();
				System.out.print(current.data+" ");
				if(current.left!=null){
					queue.offer(current.left);
				}
				if(current.right!=null){
					queue.offer(current.right);
				}
			}
			
		}
	}
	
	public void MLRTree(Node root){
		if(root!=null){
			System.out.print(root.data+" ");
			MLRTree(root.left);
			MLRTree(root.right);
		}
	}
	
	public void LMRTree(Node root){
		if(root!=null){
			MLRTree(root.left);
			System.out.print(root.data+" ");
			MLRTree(root.right);
		}
	}
	
	public void LRMTree(Node root){
		if(root!=null){
			MLRTree(root.left);
			MLRTree(root.right);
			System.out.print(root.data+" ");
		}
	}
	
	public int getMinData(Node root){
		Node current = root;
		if(root == null){
			return 0;
		}else{
			while(true){
				if(current.left==null){
					return current.data;
				}
				current = current.left;
			}
		}
		
	}
	
	public int getMaxData(Node root){
		Node current = root;
		if(root == null){
			return 0;
		}else{
			while(true){
				if(current.right==null){
					return current.data;
				}
				current = current.right;
			}
		}
		
	}
	
	public boolean deleteNode(int data){
		Node current = root;
		Node parent = null;
		boolean isLeftChild = true;
		while(true){
			if(data ==current.data){
				break;
			}else if(data < current.data){
				isLeftChild = true;
				parent = current;
				current = parent.left;
			}else{
				isLeftChild = false;
				parent = current;
				current = parent.right;
			}
			
			if(current == null){
				return false;
			}
		}
		
		if(current.left==null && current.right==null){
			if(current == root){
				root = null;
			}else{
				if(isLeftChild){
					parent.left = null;
				}else{
					parent.right = null;
				}
			}
		}else if(current.right == null){
			if(current == root){
				root = current.left;
			}else{
				if(isLeftChild){
					parent.left = current.left;
				}else{
					parent.right = current.left;
				}
			}
		}else if(current.left == null){
			if(current == root){
				root = current.right;
			}else{
				if(isLeftChild){
					parent.left = current.right;
				}else{
					parent.right = current.right;
				}
				return false;
			}
		}else{
			return false;
		}
		return false;
	}
}
